public class Test10 {
    /**
     * 106. 从中序与后序遍历序列构造二叉树
     * 给定两个整数数组 inorder 和 postorder ，
     * 其中 inorder 是二叉树的中序遍历，
     * postorder 是同一棵树的后序遍历，
     * 请你构造并返回这颗 二叉树 。
     */
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) {
          this.val = val;
      }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    public int i = 0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        i = postorder.length-1;
        return buildTreeChild(postorder,inorder,0,inorder.length-1);
    }

    public TreeNode buildTreeChild(int[] postorder, int[] inorder,
                                          int inbegin, int inend) {
        if(inbegin > inend) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[i]);
        //找到当前根，在中序遍历的位置
        int rootIndex = findIndex(inorder,inbegin,inend,postorder[i]);
        i--;

        root.right = buildTreeChild(postorder,inorder,rootIndex+1,inend);
        root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1);
        return root;
    }

    private int findIndex( int[] inorder,int inbegin,int inend, int key) {
        for(int i = inbegin;i <= inend; i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
}
